1. Field of Invention
The present invention relates generally to methods and apparatus for improving the performance of software applications. More particularly, the present invention relates to methods and apparatus for reducing the overhead associated with allowing a thread to effectively own an object.
2. Description of the Related Art
In object-based computing systems, objects are generally operated on by threads. An object typically includes a set of operations and a state that remembers the effect of the operations. Since an object has some memory capability, an object differs from a function, which has substantially no memory capability. A thread, as will be understood by those skilled in the art, is essentially a single sequential flow of control within a computer program. In general, a thread, or a xe2x80x9cthread of control,xe2x80x9d is a sequence of central processing unit (CPU) instructions or programming language statements that may be independently executed. Each thread has its own execution stack on which method activations reside.
During the execution of an object-based program, multiple threads may attempt to execute operations which involve a single object. Frequently, only one thread is allowed to invoke one of some number of operations, i.e., synchronized operations, that involve a particular object at any given time. That is, only one thread may be allowed to execute a synchronized operation on a particular object at one time. A synchronized operation, e.g., a synchronized method, is block-structured in that it requires that the thread invoking the method to first synchronize with the object that the method is invoked on, and desynchronize with that object when the method returns. Synchronizing a thread with an object generally entails controlling access to the object using a synchronization construct before invoking the method.
Since a thread, e.g., a concurrent thread as will be appreciated by those skilled in the art, is not able to predict when it will be forced to relinquish control, synchronization constructs such as locks, mutexes, semaphores, and monitors may be used to control access to shared resources during periods in which allowing a thread to operate on shared resources would be inappropriate. By way of example, in order to prevent more than one thread from operating on an object at any particular time, objects are often provided with locks. The locks are arranged such that only the thread that has possession of the lock for an object is permitted to execute a method on that object.
With reference to FIG. 2, the steps associated with locking an object will be described. A process 104 of locking an object begins at step 108 in which object information associated with the object is obtained by the thread that is attempting to lock the object, i.e., the current thread. While the object information that is obtained may vary, the object information generally includes bits or pointers which identify whether the object is already locked.
After the object information is obtained, a determination is made in step 112 as to whether the object is locked by another thread, or a thread which is not the current thread. If the determination is that the object is locked by another thread, then process control moves to step 116 in which the current thread blocks itself. By blocking itself, the current thread may effectively put itself to sleep, or otherwise cease execution, until notification is received that the object is no longer locked. When notification that the object is available is received in step 120, then the current thread unblocks itself and obtains the object lock in step 124. By obtaining the object lock, the current thread becomes the owner of the object, and is allowed to operate on the object. Hence, the process of locking the object is completed.
Alternatively, when it is determined in step 112 that the object is not locked by another thread, then a determination is made in step 128 regarding whether the current thread has already locked the object. In other words, the current thread determines whether it holds the lock on the object. If it is determined that the current thread has not already locked the object, then the indication is that the object is not locked. Accordingly, process flow moves to step 136 where a locking record in the object information is updated to indicate that the object is locked, or owned, by the current thread. When there is no existing locking record, then a new locking record is created, and set to indicate that the object is locked by the current thread. Once the locking record is either updated or set, the process of locking the object is completed.
Returning to step 128, if the determination is that the object is already locked by the current thread, then in step 132 the locking record in the object information is updated to indicate the depth of the lock. Indicating the depth of the lock effectively identifies how many separate operations the current thread is either performing or attempting to perform on the object. The indication of the depth of the lock prevents the current thread from releasing the lock prematurely, e.g., before the current thread is finished operating on the object, as will be appreciated by those skilled in the art. After the depth of the lock is updated, the process of locking the object is completed.
In order to prevent a thread from acquiring ownership of an object while another thread is studying the object, e.g., attempting to lock the object, operations associated with locking an object are performed atomically. That is, the sequence of operations associated with locking an object is essentially performed all at once. The use of atomic operations is computationally expensive and, as a result, an object locking process is expensive.
Some objects or data structures, such as vectors and hash tables, are effectively implemented in a single-threaded manner. That is, ownership of such objects or data structures is rarely contested. However, despite the fact that some objects or data structures are substantially always used by the same thread, the objects or data structures still include locks. Therefore, whenever the thread wishes to operate on or use such objects or data structures, a locking procedure is performed. As previously mentioned, a locking procedure includes atomic operations which are computationally costly. The performance of an expensive locking procedure on an object whose ownership will generally not be contested may unnecessarily increase the overhead associated with the execution of an object-based program, since substantially only the owner thread will ever attempt to operate on the object.
Therefore, what is desired is a method for reducing the cost associated with locking an object whose ownership is not typically contested. That is, what is needed is an efficient method for allowing an object to be operated on by a thread when the thread has not actually locked the object.
The present invention relates to an object which may be speculatively locked such that a thread may operate on the object without acquiring the actual lock associated with the object. Enabling a thread to effectively possess an object without actually owning the object reduces the locking overhead associated with an overall computing system, thereby improving the performance of the computing system. According to one aspect of the present invention, a method for acquiring use of an object using a current thread includes a determination of whether a first bit associated with the object is set to indicate that the object is speculatively owned by a speculative owner thread. When the object is speculatively owned, the speculative owner thread is allowed to use the object without locking the object. The method also includes checking a stored identifier that is associated with the object and identifies the speculative owner thread, as well as determining whether the stored identifier identifies the current thread. When the stored identifier identifies the current thread, the current thread already has use of the object; i.e., the current thread is the speculative owner thread. Finally, the method includes locking the object using the speculative owner thread when it is determined that the stored identifier does not identify the current thread.
In one embodiment, as for example when substantially all objects in a computing system are known to be suitable for speculative ownership, the stored identifier is checked before determining when the first bit associated with the object is set to indicate that the object is associated with the speculative owner thread. In another embodiment, the current thread calls a safepoint during which the object is locked using the speculative owner thread. In such an embodiment, locking the object involves identifying at least one stack frame in the thread stack of the speculative owner thread that has an associated locking record and modifying, or otherwise setting, the locking record to identify the object as being locked by the speculative owner thread.
According to another aspect of the present invention, a computer-implemented method for acquiring ownership of an object in a threaded system includes assigning non-locked ownership, e.g., speculative ownership, of the object to a first thread. Assigning non-locked ownership of the object to the first thread enables the first thread to operate on the object without possessing an ownership lock associated with the object. The method also includes attempting to obtain the ownership lock associated with the object using a second thread. Attempting to obtain the ownership lock associated with the object using the second thread includes causing the first thread to acquire possession of the ownership lock. In one embodiment, assigning non-locked ownership of the object to the first thread includes setting bits, which are separate from bits associated with an ownership lock, in the object to associate the object with the first thread.
In accordance with still another aspect of the present invention, an object-based computing system includes a speculative owner thread, which has an associated stack, and an object. The computing system includes a first determinator that determines when a first bit associated with the object is set to indicate that the object is associated with the speculative owner thread. The speculative owner thread may use the object without locking the speculative owner thread. The computing system also includes a checking mechanism that checks a stored identifier that is stored in the object and identifies the speculative owner thread. A second determinator in the computing system determines whether the stored identifier identifies the current thread, and a locking mechanism is arranged to lock the object with respect to the speculative owner thread when it is determined that the stored identifier does not identify the first thread.
These and other advantages of the present invention will become apparent upon reading the following detailed descriptions and studying the various figures of the drawings.